<?php

namespace app\api\controller;

use app\common\controller\Api;

use fast\Random;
use think\Db;

define('INFINITY', 9999999);

class PointX
{
    public $x;// x坐标
    public $y;// y坐标
    public $g;// 移动权重
    public $h;// 目标权重
    public $f;// 总权重
    public $fatherpoint;// 父节点

    public function init($x, $y, $g, $h, $f, $fatherPoint)
    {
        $this->x = $x;
        $this->y = $y;
        $this->g = $g;
        $this->h = $h;
        $this->f = $f;
        $this->fatherpoint = $fatherPoint;
    }
}

class CBox
{
    public $type = 0; //0-空地 1-货架｜障碍物
    public $width = 1;//Box的宽度 米
    public $nodeID = 0;// Box在仓库里的编号 for 演算;  10000*j + i
    public $i = 0;//1~200
    public $j = 0;//1~200

    public function init($type, $i, $j)
    {
        $this->type = $type;
        $this->i = $i;
        $this->j = $j;
//        $this->nodeID = 10000*$j + $i;
    }
}


class Astar extends Api
{
    // 无需登录的接口,*表示全部
    protected $noNeedLogin = ['*'];
    // 无需鉴权的接口,*表示全部
    protected $noNeedRight = ['*'];

    protected $rect = [];// 地图矩阵 x , y
    protected $xMax = 0;//1~200
    protected $yMax = 0;//1~200

    protected $nowx = 0;// 起点x
    protected $nowy = 0;// 起点y
    protected $endx = 0;// 终点x
    protected $endy = 0;// 终点y

    protected $list_open = [];// 保存开放列表
    protected $list_close = [];// 保存关闭列表
    protected $list_result = [];// 保存最终路径列表
    protected $ccBoxlist = [];

    protected $every_width = 0;// 每个方块的宽度
    protected $every_height = 0;// 每个方块的高度

    //http://ela.test/api/astar/test
    public function test()
    {
        set_time_limit(0); //执行时间无限
        ini_set('memory_limit', '-1'); //内存无限

        ob_end_clean();
        ob_implicit_flush();
        header('X-Accel-Buffering: no');

        echo '#Begin' . date('H:i:s') . '<br>';

        $this->xMax = 1000;
        $this->yMax = 1000;

        $this->nowx = 1;// 起点x
        $this->nowy = 1;// 起点y
        $this->endx = $this->xMax - 2;// 终点x
        $this->endy = $this->yMax - 2;// 终点y

        $this->ccBoxlist = [];
        for ($j = 0; $j < $this->yMax; $j++) {
            for ($i = 0; $i < $this->xMax; $i++) {
                $box = new CBox();
                $type = 0;
                if ($i == 0 || $j == 0 || $i == $this->xMax-1 || $j == $this->yMax-1  ) {
                    $type = 1; //外围都是货架
                }
                $box->i = $i;
                $box->j = $j;
                $box->type = $type;
//                $box->init($type, $i, $j); //调用函数很慢
                $this->ccBoxlist[] = $box;

                if ($i == 1 && $j == 1) {
                    $A = $box;//起点
                } else if ($i == $this->endx && $j == $this->endy) {
                    $B = $box;//起点
                }
            }
        }
        echo '111' . date('H:i:s') . '<br>';
    }

    //http://ela.test/api/astar/route
    public function route()
    {
        set_time_limit(0); //执行时间无限
        ini_set('memory_limit', '-1'); //内存无限

        ob_end_clean();
        ob_implicit_flush();
        header('X-Accel-Buffering: no');

        echo '#Begin' . date('H:i:s') . '<br>';

        $this->xMax = 60;
        $this->yMax = 60;

        $this->nowx = 1;// 起点x
        $this->nowy = 1;// 起点y
        $this->endx = $this->xMax - 2;// 终点x
        $this->endy = $this->yMax - 2;// 终点y

        $this->ccBoxlist = [];
        for ($j = 0; $j < $this->yMax; $j++) {
            for ($i = 0; $i < $this->xMax; $i++) {
                $box = new CBox();
                $type = 0;
                if ($i == 0 || $j == 0 || $i == $this->xMax-1 || $j == $this->yMax-1  ) {
                    $type = 1; //外围都是货架
                }
                $box->i = $i;
                $box->j = $j;
                $box->type = $type;
                $this->ccBoxlist[] = $box;

                if ($i == 1 && $j == 1) {
                    $A = $box;//起点
                } else if ($i == $this->endx && $j == $this->endy) {
                    $B = $box;//起点
                }
            }
        }
        echo '111' . date('H:i:s') . '<br>';

        //开始算 updateRun
        $this->list_result = [];
        $this->list_open = [];
        $this->list_close = [];

        $pointA = new PointX();
        $pointA->init(1, 1, 0, abs($this->endx - 1) + abs($this->endy - 1),
            abs($this->endx - 1) + abs($this->endy - 1), null);
        $this->list_close[] = $pointA;

        $isLooper = true;
        while ($this->isinEnd() == false && $isLooper) {
            // 将符合条件的节点加入开放列表
            foreach ($this->list_close as $k => &$v) {
                $this->addPoint($v);
            }

            // 更新关闭列表和开放列表中的节点
            if ($this->updatePoint() == false) {
                $this->list_result = [];
                $this->list_open = [];
                $this->list_close = [];
                $isLooper = false;
            }
        }
        // 将最终结果筛选，并保存到最终路径列表中
        $this->refreshPoint();

        $distance = 0;
        $pxLast = null;
        $nodelink = "";
        $i = 0;
        foreach ($this->list_result as $k => &$v) {
            $strnode = "(".$v->x . "," . $v->y.")";
            if ($i == 0) {
                $nodelink = $strnode;
            } else {
                $nodelink = $nodelink . "-" . $strnode;

                if ($v->x == $pxLast->x || $v->y == $pxLast->y) {
                    //上下左右走
                    $distance += 1;
                } else {
                    //斜走
                    $distance += 1.414;
                }
            }
            $pxLast = $v;
            $i++;
        }

        echo "distance=".$distance." path=".$nodelink.'<br>#OK ' . date('H:i:s') . '<br>';
    }

    function refreshPoint()
    {
        // 获得最终路径列表
        if (count($this->list_close) != 0) {
            $endPoint = end($this->list_close);
            while ($endPoint != null) {
                $this->list_result[] = $endPoint;
                $endPoint = $endPoint->fatherpoint;
            }
        }
        $this->list_result = array_reverse($this->list_result);
    }

    function updatePoint()
    {
        $minPoint = null;

        $select = 0;
        foreach ($this->list_open as $k => &$v) {
            if ($minPoint == null) {
                $minPoint = $v;
                $select = $k;
            } else {
                if ($minPoint->f >= $v->f) {
                    $minPoint = $v;
                    $select = $k;
                }
            }
        }

        if ($minPoint != null) {
            $pointA = new PointX();
            $pointA->init($minPoint->x, $minPoint->y, $minPoint->g, $minPoint->h, $minPoint->f, $minPoint->fatherpoint);
            $this->list_close[] = $pointA;
            unset($this->list_open[$select]);
            return true;
        } else {
            return false;
        }
    }

    // 检查当前节点周围节点
    function addPoint($p)
    {
        $arrow_up = 0;
        $arrow_down = 0;
        $arrow_left = 0;
        $arrow_right = 0;

        // 判断是否越界
        if ($this->isOut($p->x, $p->y-1) || $this->isCanMove($p->x, $p->y-1) == false)
            $arrow_up = 1;
        if ($this->isOut($p->x, $p->y+1) || $this->isCanMove($p->x, $p->y+1) == false)
            $arrow_down = 1;
        if ($this->isOut($p->x-1, $p->y) || $this->isCanMove($p->x-1, $p->y) == false)
            $arrow_left = 1;
        if ($this->isOut($p->x+1, $p->y) || $this->isCanMove($p->x+1, $p->y) == false)
            $arrow_right = 1;

        // 如果arrow方向所对应的值仍然为0，那么判断节点是否在关闭列表中
        foreach ($this->list_close as $k => &$v) {
            $tempx = $v->x;
            $tempy = $v->y;
            if ($arrow_up == 0 && $tempx == $p->x && $tempy == $p->y - 1) {
                $arrow_up = 1;
            } else if ($arrow_down == 0 && $tempx == $p->x && $tempy == $p->y + 1) {
                $arrow_down = 1;
            } else if ($arrow_left == 0 && $tempx == $p->x - 1 && $tempy == $p->y) {
                $arrow_left = 1;
            } else if ($arrow_right == 0 && $tempx == $p->x + 1 && $tempy == $p->y) {
                $arrow_right = 1;
            }
        }

        // 如果arrow方向所对应的值仍然为0，那么判断节点是否在开放列表中
        foreach ($this->list_open as $k => &$v) {
            $tempx = $v->x;
            $tempy = $v->y;
            if ($arrow_up == 0 && $tempx == $p->x && $tempy == $p->y - 1) {
                $arrow_up = 1;
            } else if ($arrow_down == 0 && $tempx == $p->x && $tempy == $p->y + 1) {
                $arrow_down = 1;
            } else if ($arrow_left == 0 && $tempx == $p->x - 1 && $tempy == $p->y) {
                $arrow_left = 1;
            } else if ($arrow_right == 0 && $tempx == $p->x + 1 && $tempy == $p->y) {
                $arrow_right = 1;
            }
        }

        // 将符合条件的节点加入开放列表中
        if ($arrow_up == 0) {
            $pointA = new PointX();
            $pointA->init($p->x, $p->y - 1, $p->g + 1, abs($p->x - $this->endx) + abs($p->y - 1 - $this->endy),
                $p->g + 1 + abs($p->x - $this->endx) + abs($p->y - 1 - $this->endy), $p);
            $this->list_open[] = $pointA;
        }
        if ($arrow_down == 0) {
            $pointA = new PointX();
            $pointA->init($p->x, $p->y + 1, $p->g + 1, abs($p->x - $this->endx) + abs($p->y + 1 - $this->endy),
                $p->g + 1 + abs($p->x - $this->endx) + abs($p->y + 1 - $this->endy), $p);
            $this->list_open[] = $pointA;
        }
        if ($arrow_left == 0) {
            $pointA = new PointX();
            $pointA->init($p->x - 1, $p->y, $p->g + 1, abs($p->x - 1 - $this->endx) + abs($p->y - $this->endy),
                $p->g + 1 + abs($p->x - 1 - $this->endx) + abs($p->y - $this->endy), $p);
            $this->list_open[] = $pointA;
        }
        if ($arrow_right == 0) {
            $pointA = new PointX();
            $pointA->init($p->x + 1, $p->y, $p->g + 1, abs($p->x + 1 - $this->endx) + abs($p->y - $this->endy),
                $p->g + 1 + abs($p->x + 1 - $this->endx) + abs($p->y - $this->endy), $p);
            $this->list_open[] = $pointA;
        }
    }

    // x,y是否可以移动
    function isCanMove($i, $j)
    {
        for ($m = 0; $m < count($this->ccBoxlist); $m++) {
            if ($this->ccBoxlist[$m]->i == $i && $this->ccBoxlist[$m]->j == $j) {
                if ($this->ccBoxlist[$m]->type == 1) {
                    return false;
                }
                break;
            }
        }

        return true;
    }

    // x,y是否出界
    function isOut($x, $y) {
        if ($x < 0 || $x >= $this->xMax || $y < 0 || $y >= $this->yMax)
            return true;
        else
            return false;
    }

    // 终点x,y是否在关闭列表中
    function isinEnd()
    {
        for ($i = 0; $i < count($this->list_close); $i++) {
            $tempx = $this->list_close[$i]->x;
            $tempy = $this->list_close[$i]->y;
            if ($tempx == $this->endx && $tempy == $this->endy) {
                return true;
            }
        }
        return false;
    }

}


